#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    // int largestRectangleArea(vector<int> &heights)
    // {
    //     int result = 0;
    //     int size = heights.size();
    //     for (int i = 0; i < size; i++)
    //     {
    //         int left = i;
    //         int right = i;
    //         for (; left >= 0; left--)
    //         {
    //             if (heights[left] < heights[i])
    //             {
    //                 break;
    //             }
    //         }
    //         for (; right <= size - 1; right++)
    //         {
    //             if (heights[right] < heights[i])
    //             {
    //                 break;
    //             }
    //         }
    //         int sum = (right - left - 1) * heights[i];
    //         result = max(result, sum);
    //     }
    //     return result;
    // }

    // int largestRectangleArea(vector<int> &heights)
    // {
    //     int size=heights.size();
    //     vector<int> left_index(size);
    //     vector<int> right_index(size);
    //     left_index[0]=-1;
    //     for(int i=1;i<size;i++)
    //     {
    //         int t=i-1;
    //         while(t>=0&&heights[t]>=heights[i])
    //         {
    //             t=left_index[t];
    //         }
    //         left_index[i]=t;
    //     }
    //     right_index[size-1]=size;
    //     for(int i=size-2;i>=0;i--)
    //     {
    //         int t=i+1;
    //         while(t<=size-1&&heights[t]>=heights[i])
    //         {
    //             t=right_index[t];
    //         }
    //         right_index[i]=t;
    //     }
    //     int max_rectangle=0;
    //     for(int i=0;i<size;i++)
    //     {
    //         int sum=(right_index[i]-left_index[i]-1)*heights[i];
    //         max_rectangle=max(max_rectangle,sum);
    //     }
    //     return max_rectangle;
    // }

    int largestRectangleArea(vector<int> &heights)
    {
        int result = 0;
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        int size = heights.size();
        stack<int> stk;
        stk.push(0);
        for (int i = 1; i < size; i++)
        {
            if (heights[i] > heights[stk.top()])
            {
                stk.push(i);
            }
            else if (heights[i] == heights[stk.top()])
            {
                stk.pop();
                stk.push(i);
            }
            else
            {
                while (!stk.empty() && heights[i] < heights[stk.top()])
                {
                    int mid = stk.top();
                    stk.pop();
                    if (!stk.empty())
                    {
                        int w = i - stk.top() - 1;
                        int h = heights[mid];
                        int sum = w * h;
                        result = max(result, sum);
                    }
                }
                stk.push(i);
            }
        }
        return result;
    }
};

int main()
{
    vector<int> heights{2, 1, 5, 6, 2, 3};
    Solution sol;
    cout << sol.largestRectangleArea(heights) << endl;
    return 0;
}